The present invention relates generally to information retrieval from electronic storage devices, and more particularly, to a method and system for private information retrieval from an electronic storage device using one or more servers.
With the advancement of Internet communications, the need for private information retrieval is increasing. For example, if a company maintains an Internet website with a complete listing of patents, competitors may be interested in searching those patents when introducing competitive products or services. Without privacy from the inquirer, the company can monitor database inquiries into its patent portfolio and gain knowledge as to the identity of the patents in which the competitors are interested. Thus, there is a need for privately retrieving selected information from an electronic storage device such that the information is not revealed to the storage device.
Private information retrieval ("PIR") schemes allow a user to retrieve information from an electronic storage device while maintaining the privacy of the queries from the electronic storage device. As used herein, "electronic storage device" refers to any processing system that stores information that a user at an inquiring processor may wish to retrieve. Moreover, the terms "electronic storage device" and "database" will be used interchangeably and should be understood in their broadest sense.
The least sophisticated method for performing a private information retrieval is to request a copy of the entire database. This, of course, hides the particular information sought by the inquiring processor, but requires an impractical exchange of information between the database and the inquiring processor. Moreover, when a database is large and its contents frequently change, the inquiring processor must receive frequent and possibly costly updates whenever the database changes.
Another PIR method requires replication of the database at alterative sites that do not communicate with one another. This replication technique is disclosed in B. Chor and O. Goldreich et al., "Private Information Retrieval," 36th Annual IEEE Symposium On Foundations Of Computer Science (1995), A. Ambainis, "Upper Bound On The Communication Complexity Of Private Information Retrieval," in the proceedings of 24th International Colloquium on Automata Languages and Programming, Volume 1256 (1997), B. Chor and N. Gilboa, "Computationally Private Information Retrieval," 29th Symposium On The Theory Of Computing, and R. Ostrovsky and V. Shoup, "Private Information Storage," 29th Symposium On The Theory Of Computing. To assure privacy of the requested information, this method requires replication of the database at alternative sites that do not communicate with one another.
An improved PIR method that does not require replication of a database at alternative sites is disclosed in pending U.S. patent application Ser. No. 09/087,893, entitled "Method And Apparatus For Private Information Retrieval From A Single Electronic Storage Device," and E. Kushilevitz and R. Ostrovsky, "Replication Is Not Needed: Single Database, Computationally Private Information Retrieval," in the proceedings of 38.sup.th Annual IEEE Symposium on the Foundations of Computer Science (1997). This improved PIR method privately retrieves selected information from a portion of or an entire database without revealing to the database the address of the selected information. The method conceals the address of selected information in an encoding function that hides or conceals the address from the database. The database applies the encoding function to the relevant portion of database, and returns the result back to an inquiring processor. A disadvantage of the method is the attendant complexities associated with determining, at the inquiring processor, an encoding function that can conceal the address of the selected information from the database.
Another method, which uses a plurality of servers, is disclosed in D. Beaver, "Commodity-Based Cryptography," in the proceedings of 29th Symposium Of Theory Of Computing (1997), pages 446-455. The Beaver method describes an oblivious transfer protocol for private information exchange between an inquiring processor and a database. The inquiring processor and the database receive from a plurality of servers commodities, which the inquiring processor and the database use to privately exchange information with each other. The Beaver method, however, has two disadvantages: First, it does not reduce the attendant complexities associated with privately retrieving selected information from a database. Second, to assure private information retrieval, the Beaver method requires that at least half of the servers do not communicate with one another, a requirement which may not be practically enforced against servers.
Therefore, it is desirable to have a method and system for private information retrieval which overcome the disadvantages of the prior art.